Programming Interviews Exposed by John Mongan & Eric Giguère & Noah Kindler
Author:John Mongan & Eric Giguère & Noah Kindler
Language: eng
Format: epub
Publisher: John Wiley & Sons, Inc.
Published: 2012-11-09T16:00:00+00:00
Multi-Key Sort
PROBLEM You have an array of objects, each of which represents an employee:
public class Employee { public String extension; public String givenname; public String surname; }
Using a standard library sorting routine, sort the array so it is ordered alphabetically by surname and then by given name as in a company phone book.
To sort the data using a routine from the standard library, you need a comparator: a function that compares two objects. A comparator returns a negative value if the first object is “less than” the second object; zero if the two objects have equal keys; or a positive value if the first object is “greater than” the second.
For this problem, there are two components of the key: The surname and the given name, so the comparator needs to use both of these values. You must order first by surname and then by given name, so the comparator should start by comparing the surnames and then resolve ties by comparing the given names.
In Java, comparators implement the java.util.Comparator interface:
import java.util.Comparator; // A comparator for Employee instances. public class EmployeeNameComparator implements Comparator<Employee> { public int compare( Employee e1, Employee e2 ){ // Compare surnames int ret = e1.surname.compareToIgnoreCase( e2.surname ); if( ret == 0 ){ //Compare givennames if surnames are the same ret = e1.givenname.compareToIgnoreCase( e2.givenname ); } return ret; } }
Now it’s just a matter of invoking the Arrays.sort method with the array and the comparator:
public void sortEmployees( Employee[] employees ){ Arrays.sort( employees, new EmployeeNameComparator() ); }
The approach shown here of using a comparator that considers both parts of the key in a single sort is the most efficient approach, but there is another alternative. If the sort routine you use is stable (the modified merge sort used by Arrays.sort is), you can achieve the same result by calling the sort routine twice and sorting on one part of the key at a time. For this problem, you would first sort by given name and then make a second call to sort by surname. During the second sort, by the definition of a stable sort, employees with the same surname would retain their relative ordering based on given name, established by the first sort.
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Coding Theory | Localization |
Logic | Object-Oriented Design |
Performance Optimization | Quality Control |
Reengineering | Robohelp |
Software Development | Software Reuse |
Structured Design | Testing |
Tools | UML |
Deep Learning with Python by François Chollet(12571)
Hello! Python by Anthony Briggs(9916)
OCA Java SE 8 Programmer I Certification Guide by Mala Gupta(9796)
The Mikado Method by Ola Ellnestam Daniel Brolund(9779)
Dependency Injection in .NET by Mark Seemann(9340)
Algorithms of the Intelligent Web by Haralambos Marmanis;Dmitry Babenko(8300)
Test-Driven iOS Development with Swift 4 by Dominik Hauser(7763)
Grails in Action by Glen Smith Peter Ledbrook(7696)
The Well-Grounded Java Developer by Benjamin J. Evans Martijn Verburg(7557)
Becoming a Dynamics 365 Finance and Supply Chain Solution Architect by Brent Dawson(7084)
Microservices with Go by Alexander Shuiskov(6854)
Practical Design Patterns for Java Developers by Miroslav Wengner(6772)
Test Automation Engineering Handbook by Manikandan Sambamurthy(6711)
Secrets of the JavaScript Ninja by John Resig Bear Bibeault(6417)
Angular Projects - Third Edition by Aristeidis Bampakos(6117)
The Art of Crafting User Stories by The Art of Crafting User Stories(5647)
NetSuite for Consultants - Second Edition by Peter Ries(5579)
Demystifying Cryptography with OpenSSL 3.0 by Alexei Khlebnikov(5385)
Kotlin in Action by Dmitry Jemerov(5065)
